package com.lw.leetcode.sort.c;

import com.lw.test.util.Utils;

import java.util.Map;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * 1425. 带限制的子序列和
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/27 17:53
 */
public class ConstrainedSubsetSum {

    public static void main(String[] args) {
        ConstrainedSubsetSum test = new ConstrainedSubsetSum();

        // 37
//        int[] arr = {10, 2, -10, 5, 20};
//        int k = 2;

        // -1
//        int[] arr = {-1, -2, -3};
//        int k = 1;

        // 23
//        int[] arr = {10, -2, -10, -5, 20};
//        int k = 2;

        // 23
        int[] arr = Utils.getArr(100000, -10000, 10000);
        int k = 1256;
        System.out.println(k);

        int i = test.constrainedSubsetSum(arr, k);
        System.out.println(i);
    }

    public int constrainedSubsetSum(int[] nums, int k) {
        TreeMap<Long, Integer> map = new TreeMap<>();
        int length = nums.length;
        int max = Integer.MIN_VALUE;
        long[] arr = new long[length];
        arr[0] = nums[0];
        int index = 0;
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            int st = Math.max(-1, i - k);
            for (int j = index; j < st; j++) {
                Map.Entry<Long, Integer> en = map.floorEntry(arr[j]);
                int v = en.getValue();
                if (v == 1) {
                    map.remove(en.getKey());
                } else {
                    map.put(en.getKey(), v - 1);
                }
            }
            index = Math.max(index, st);
            Map.Entry<Long, Integer> entry = map.lastEntry();
            long key = num;
            if (entry != null) {
                key = Math.max(key, key + entry.getKey());
            }
            map.put(key, map.getOrDefault(key, 0) + 1);
            arr[i] = key;
            max = (int) Math.max(max, key);
        }
        return max;
    }

}
